package Chapter1_1Text;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;

public class BinarySearch {  //二分查找算法（重要）
    public static int rank(int key, int[] a) {
        //数组必须为有序的
        Arrays.sort(a);
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            //被查找的键要么不存在，要么必然存在于a[lo+hi]之中
            int mid = lo + (hi - lo) / 2;  //也可以为(lo + hi) >> 1，二进制中按位向右移一位等同于除以2
            if (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] whitelist = In.readInts(args[0]);
        while (!StdIn.isEmpty()) { //读取键值，如果不存在于白名单中则将其打印
            int key = StdIn.readInt();
            if (rank(key, whitelist) < 0)
                StdOut.println(key);
        }
    }
}
